/* ==========================================================================
 * maze.js
 *
 * Written by Kostas Symeonidis
 * Copyright (c)1996, 2004, 2011
 * ==========================================================================
 * History:
 *
 * 30.May.2011  Started
 * ==========================================================================
 * "Maze JS" License
 * GNU General Public License version 3.0 (GPLv3)
 * ==========================================================================
 * This file is part of "Maze JS"
 *
 * "Maze JS" is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * "Maze JS" is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with "Maze JS". If not, see <http://www.gnu.org/licenses/>.
 * ==========================================================================
 */

// ========================================================================
// == SizeCalculator
// ========================================================================
/* ==========================================================================
 * Util.js
 *
 * Written by Kostas Symeonidis
 * Copyright (c) 2009, CyLog Software
 * ==========================================================================
 * History:
 *
 * 08.Jun.2009 Started
 * ==========================================================================
 * This is just a collection of small and useful functions
 * ==========================================================================
 * License
 * GNU General Public License version 3.0 (GPLv3)
 * ==========================================================================
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * ==========================================================================
 */

/**
 * Returns 1 for TRUE boolean values, 0 for FALSE to be used in
 * arithmetical calculations.
 *
 * @param b
 */
function booleanToInt ( b )
{
    return b ? 1 : 0;
}

/**
 * Returns a random number between 0..n-1
 * @param n
 */
function random ( n )
{
    return Math.floor(Math.random() * n);
}

/**
 * Returns a random number between n1..n2 inclusive
 * @param n1
 * @param n2
 */
function randomRange ( n1, n2 )
{
    return Math.floor(Math.random() * (n2 - n1 + 1)) + n1;
}

/**
 * Returns a random number between -(n-1)..(n-1) except 0.
 * For exammple a n=3 will give you -3,-2,-1,1,2,3 as possible answers
 * @param n
 */
function randomSignedNoZero ( n )
{
    var i = random(n * 2) - n + 1;  // -(n-1), -(n-2), ..., 0, ..., n-1, n
    return (i < 1) ? i - 1 : i;
}

/**
 * Returns a floating point random between [0..n)
 * @param n
 */
function randomFloat ( n )
{
    return Math.random() * n;
}

/**
 * Returns a floating point random between [n1..n2)
 * @param n1 from
 * @param n2 to
 */
function randomFloatRange ( n1, n2 )
{
    return Math.random() * (n2 - n1) + n1;
}

/**
 * Returns the current time in milliseconds since 1970
 */
function timeInMillis ()
{
    return (new Date()).getTime();
}

/**
 * Returns TRUE if x is between start and finish (non inclusive)
 *
 * @param x
 * @param start
 * @param finish
 */
function inRange ( x, start, finish )
{
    return (x >= start) && (x < finish);
}
function SizeCalculator ()
{
    this.tileSize = 8;
    this.rows = 40;
    this.cols = 40;
}

SizeCalculator.prototype.setupRowsCols = function ( rows, cols, tileSize )
{
    this.rows = rows;
    this.cols = cols;
    this.tileSize = tileSize;
};

SizeCalculator.prototype.setRows = function ( rows )
{
    this.rows = rows;
};

SizeCalculator.prototype.setCols = function ( cols )
{
    this.cols = cols;
};

SizeCalculator.prototype.setTileSize = function ( tileSize )
{
    this.tileSize = tileSize;
};

SizeCalculator.prototype.getCanvasWidth = function ()
{
    return this.tileSize * (this.cols + 2);
};

SizeCalculator.prototype.getCanvasHeight = function ()
{
    return this.tileSize * (this.rows + 2);
};

// ========================================================================
// == End of SizeCalculator
// ========================================================================

// ========================================================================
// == Cell
// ========================================================================

function Cell ( r, c )
{
    this.row = r;
    this.col = c;
}

Cell.prototype.getRow = function ()
{
    return this.row;
}

Cell.prototype.getCol = function ()
{
    return this.col;
};

// ========================================================================
// == End of Cell
// ========================================================================

// ========================================================================
// == Maze
// ========================================================================

// ---- Global Constants --------------------------------------------------

var NO_EXIT = 0x00;
var EXIT_EAST = 0x01;
var EXIT_NORTH = 0x02;
var EXIT_WEST = 0x04;
var EXIT_SOUTH = 0x08;

var CELL_INCLUDED = 0x10;     // cell has been included in the maze, during generation
var CELL_FRONTIER = 0x20;     // cell is a frontier cell (during generation)
var CELL_VISITED = 0x40;      // cell has been visited by the solving algorithm
var CELL_SOLUTION = 0x80;     // cell is part of the solution
var CELL_ENTRANCE = 0x100;
var CELL_CLEAR_SOLUTION = 0xff3f;  // mask used for "AND" in order to clear the Solution and visited cells.
var CELL_EXIT = 0x200;

var DIR_EAST = 0;
var DIR_NORTH = 1;
var DIR_WEST = 2;
var DIR_SOUTH = 3;

var DCOL = [1, 0, -1, 0];  // E-N-W-S
var DROW = [0, -1, 0, 1];  // E-N-W-S

/**
 * Creates the Axes tdPoints and sets them up
 */
function Maze ( rows, cols, tileSize, traceSize )
{
    this.MIN_COLS = 2;
    this.MIN_ROWS = 2;
    this.MAX_ROWS = 1024;
    this.MAX_COLS = 1024;

    this.rows = rows;
    this.cols = cols;
    this.tileSize = tileSize;
    this.traceSize = traceSize;

    this.sc = new SizeCalculator();
}

/**
 * Sets up the parameters of the maze, usually called before generation
 *
 * @param rows
 * @param cols
 * @param tileSize
 * @param traceSize
 */
Maze.prototype.setupParameters = function ( rows, cols, tileSize, traceSize, showVisited )
{
    this.rows = rows;
    this.cols = cols;
    this.tileSize = tileSize;
    this.traceSize = traceSize;
    this.showVisited = showVisited;

    this.sc.setupRowsCols(rows, cols, tileSize);

    this.generating = false;
};

Maze.prototype.initialiseAndClearMaze = function ()
{
    this.maze = new Array(this.rows);
    for (var i = 0; i < this.rows; i++)
    {
        this.maze[i] = new Array(this.cols);
        for (var j = 0; j < this.cols; j++)
        {
            this.maze[i][j] = NO_EXIT;
        }
    }
};

Maze.prototype.clearSolution = function ()
{
    for (var i = 0; i < this.rows; i++)
    {
        for (var j = 0; j < this.cols; j++)
        {
            this.maze[i][j] = this.maze[i][j] & CELL_CLEAR_SOLUTION;
        }
    }
};

/**
 * Returns TRUE if the given coordinate is within the size of the maze
 * @param row
 * @param col
 */
Maze.prototype.withinMazeBorders = function ( row, col )
{
    return (row >= 0) && (row < this.rows) && (col >= 0) && (col < this.cols);
};

/**
 * Marks all neighbouring cells as frontier cells as long as they are within the maze's
 * borders and they have not been visited before not are frontier cells already.
 *
 * @param row
 * @param col
 */
Maze.prototype.markFrontierCells = function ( row, col )
{
    for (var i = 0; i < 4; i++)
    {
        var r = row + DROW[i];
        var c = col + DCOL[i];

        // alert ("marking cell "+row+","+col+" -> ("+i+") -> " + r+","+c + " "+this.withinMazeBorders(r, c));

        // if r,c within Maze and CELL not VISITED NOR FRONTIER yet, then make it a frontier cell
        if (this.withinMazeBorders(r, c) &&
            ((this.maze[r][c] & CELL_INCLUDED) != CELL_INCLUDED) &&
            ((this.maze[r][c] & CELL_FRONTIER) != CELL_FRONTIER))
        {
            //alert ("marking cell "+r+","+c);

            this.maze[r][c] = this.maze[r][c] | CELL_FRONTIER;
            this.frontierCells.push(new Cell(r, c));
        }
    }
};

Maze.prototype.removeFrontierCell = function ( row, col )
{
    this.maze[row][col] = this.maze[row][col] ^ CELL_FRONTIER;
    for (var i = 0; i < this.frontierCells.length; i++)
    {
        if ((row == this.frontierCells[i].getRow()) && (col == this.frontierCells[i].getCol()))
        {
            this.frontierCells.splice(i, 1);
            return;
        }
    }
};

Maze.prototype.removeWall = function ( row, col, direction )
{
    switch (direction)
    {
        case DIR_EAST:
            this.maze[row][col] = this.maze[row][col] | EXIT_EAST;
            this.maze[row][col + 1] = this.maze[row][col + 1] | EXIT_WEST;
            break;
        case DIR_NORTH:
            this.maze[row][col] = this.maze[row][col] | EXIT_NORTH;
            this.maze[row - 1][col] = this.maze[row - 1][col] | EXIT_SOUTH;
            break;
        case DIR_WEST:
            this.maze[row][col] = this.maze[row][col] | EXIT_WEST;
            this.maze[row][col - 1] = this.maze[row][col - 1] | EXIT_EAST;
            break;
        case DIR_SOUTH:
            this.maze[row][col] = this.maze[row][col] | EXIT_SOUTH;
            this.maze[row + 1][col] = this.maze[row + 1][col] | EXIT_NORTH;
            break;
    }

};

Maze.prototype.attachCellToTree = function ( row, col, direction )
{
    this.removeFrontierCell(row, col);
    this.maze[row][col] = this.maze[row][col] | CELL_INCLUDED;

    if (direction == null)
    {
        // find a visited neighboring cell to attach to, starting from a random direction.
        var dirStart = random(4);
        for (var i = 0; i < 4; i++)
        {
            var d = (dirStart + i) % 4;
            var r = row + DROW[d];
            var c = col + DCOL[d];

            if (this.withinMazeBorders(r, c) && ((this.maze[r][c] & CELL_INCLUDED) == CELL_INCLUDED))
            {
                this.removeWall(row, col, d);
                break;
            }
        }
    }
    else
    {
        this.removeWall(row, col, direction);
    }
};

Maze.prototype.createBranch = function ( row, col )
{
    this.attachCellToTree(row, col, null);  // null = pick a random direction
    this.markFrontierCells(row, col);
    var currRow = row;
    var currCol = col;
    var bMoved;

    do
    {
        bMoved = false;
        var dirStart = random(4);
        for (var i = 0; i < 4; i++)
        {
            var direction = (dirStart + i) % 4;
            var r = currRow + DROW[direction];
            var c = currCol + DCOL[direction];

            if (this.withinMazeBorders(r, c) && ((this.maze[r][c] & CELL_FRONTIER) == CELL_FRONTIER))
            {
                this.attachCellToTree(r, c, (direction + 2) % 4);  // opposite direction
                this.markFrontierCells(r, c);
                bMoved = true;
                currRow = r;
                currCol = c;
                break;
            }
        }

    }
    while (bMoved);
};

/**
 * Generates the maze using Prim's Algorithm. Initializes the Maze first by blocking all
 * exits, then picks a random location and starts creating branches.
 *
 */
Maze.prototype.generate = function ()
{
    this.initialiseAndClearMaze();

    var r = random(this.rows);
    var c = random(this.cols);

    this.maze[r][c] = this.maze[r][c] | CELL_INCLUDED;
    this.frontierCells = new Array();
    this.markFrontierCells(r, c);

    while (this.frontierCells.length > 0)
    {
        var n = random(this.frontierCells.length);
        this.createBranch(this.frontierCells[n].getRow(), this.frontierCells[n].getCol());
    }
};

Maze.prototype.solveRecursive = function ( row, col )
{
    this.visitedCells++;
    this.solutionLength++;
    this.maze[row][col] = this.maze[row][col] | CELL_VISITED;
    this.maze[row][col] = this.maze[row][col] | CELL_SOLUTION;

    if ((row == this.exitRow) && (col == this.exitCol))
    {
        return true;  // solved
    }

    var dirOffset = random(4);  // get a random direction
    for (var i = 0; i < 4; i++)
    {
        var direction = (dirOffset + i) % 4;
        var exitMask = 1 << direction;

        if ((this.maze[row][col] & exitMask) != 0)
        {
            var tempRow = row + DROW[direction];
            var tempCol = col + DCOL[direction];

            // if the destination cell is not yet visited
            if ((this.maze[tempRow][tempCol] & CELL_VISITED) != CELL_VISITED)
            {
                if (this.solveRecursive(tempRow, tempCol))
                {
                    return true;
                }
            }
        }
    }

    // if none of the directions was good, backtrack
    this.maze[row][col] = this.maze[row][col] ^ CELL_SOLUTION;
    this.solutionLength--;
    return false;
};
Maze.prototype.drawLine = function ( ctx, x0, y0, x1, y1 )
{
    //console.log('drawLine:'+x0+','+y0+','+x1+','+y1);
    ctx.beginPath();
    ctx.moveTo(x0 + 0.5, y0 + 0.5);
    ctx.lineTo(x1 + 0.5, y1 + 0.5);
    ctx.stroke();
};

Maze.prototype.drawRect = function ( ctx, x, y )
{
    ctx.fillRect(x, y, this.tileSize, this.tileSize);
};

Maze.prototype.drawTrace = function ( ctx, x, y )
{
    ctx.fillRect(x + Math.round((this.tileSize - this.traceSize) / 2), y + Math.round((this.tileSize - this.traceSize) / 2),
                 this.traceSize, this.traceSize);
};

Maze.prototype.render = function ( ctx)
{
    ctx.strokeStyle = "black";
    ctx.lineWidth = 1;
    ctx.lineCap = "round";
    for (var i = 0; i < this.rows; i++)
    {
        for (var j = 0; j < this.cols ; j++)
        {
            x0 = j * this.tileSize;
            y0 = i * this.tileSize;
            x1 = x0 + this.tileSize;
            y1 = y0 + this.tileSize;

            // draw the four exit blocked if required
            if ((this.maze[i][j] & EXIT_NORTH) == NO_EXIT)
            {
                this.drawLine(ctx, x0, y0, x1, y0);
            }
            if ((this.maze[i][j] & EXIT_SOUTH) == NO_EXIT)
            {
                this.drawLine(ctx, x0, y1, x1, y1);
            }
            if ((this.maze[i][j] & EXIT_WEST) == NO_EXIT)
            {
                this.drawLine(ctx, x0, y0, x0, y1);
            }
            if ((this.maze[i][j] & EXIT_EAST) == NO_EXIT)
            {
                this.drawLine(ctx, x1, y0, x1, y1);
            }

        }
    }
};
